Using Euclids Extended Algorithm:
Calculate x and y in Bézout's Identity
using (11,455)
For 2 numbers a and b and divisor d:
ax + by = d
a math | a | b math | b | d math | d | k math | k |
---|---|---|---|---|---|---|---|
Set to 1 | 1 | Set to 0 | 0 | 11 | |||
Set to 0 | 0 | Set to 1 | 1 | 455 | Quotient of 11/455 | 0 | |
1 - (0 x 0) | 1 | 0 - (0 x 1) | 0 | Remainder of 11/455 | 11 | Quotient of 455/11 | 41 |
0 - (41 x 1) | -41 | 1 - (41 x 0) | 1 | Remainder of 455/11 | 4 | Quotient of 11/4 | 2 |
1 - (2 x -41) | 83 | 0 - (2 x 1) | -2 | Remainder of 11/4 | 3 | Quotient of 4/3 | 1 |
-41 - (1 x 83) | -124 | 1 - (1 x -2) | 3 | Remainder of 4/3 | 1 | Quotient of 3/1 | 3 |
83 - (3 x -124) | 455 | -2 - (3 x 3) | -11 | Remainder of 3/1 | 0 | Quotient of 1/0 | 0 |
a = -124 and b = 3
ax + by = gcd(a,b)
11x + 455y = gcd(11